package ans.p77;

import test.Entrance;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * #      77
 * 名称   组合
 * 链接   https://leetcode-cn.com/problems/combinations
 * 题解   [842](https://leetcode-cn.com/problems/combinations/solution)
 * 通过率 76.6%
 * 难道   中等
 */

public class Solution {
    @Entrance
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> lists = new LinkedList<>();
        List<Integer> list = new LinkedList<>();
        traceback(lists, list, 1, n, k);
        return lists;
    }

    private void traceback(List<List<Integer>> res, List<Integer> list, int i, int n, int k) {
        if (list.size() == k) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int j = i; j <= n; j++) {
            list.add(j);
            traceback(res, list, j+1, n, k);
            list.remove(list.size() - 1);
        }
    }
}